﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//
public class Solution121
{
    //贪心
    public int MaxProfit2(int[] prices)
    {
        int minPrice = int.MaxValue;
        int max = 0;



        for (int i = 0; i < prices.Length; i++)
        {
            int price = prices[i];
            minPrice = Math.Min(minPrice, price);
            int profit = price - minPrice;
            max = Math.Max(max, profit);

            Console.WriteLine("minPrice:  "+ minPrice+ "   profit:  " + profit);
        }


        return max;

    }

    //动态规划
    public int MaxProfit(int[] prices)
    {
        int len = prices.Length;
        int[][] dp = new int[len][];
        for (int i = 0; i < len; i++)
        {

            dp[i] = new int[2];//0是持有，1是不持有
        }

       

        dp[0][1] = -prices[0];
        dp[0][0] = 0;

        for (int i = 1; i < prices.Length; i++)
        {
            //不持有，前一天没有，或者今天卖了
            dp[i][0]=Math.Max( dp[i-1][0], dp[i-1][1]+ prices[i]);
            //持有，前一天持有，或者今天买了(但是没有前面的状态）
            dp[i][1]=Math.Max( dp[i-1][1],-prices[i]);


            
        }


        return dp[len-1][0];

    }
}

class Program121
{


    static void Main121(string[] args)
    {
        Solution121 solution = new Solution121();

        int[] prices = [7, 1, 5, 3, 6, 4];
        int res=solution.MaxProfit(prices);
        Console.WriteLine(res);

    }
}
